/**
 * Created with IntelliJ IDEA.
 * Description:
 * 给定两个整数数组preorder 和 inorder，其中
 * preorder 是二叉树的先序遍历， inorder是同一棵树的中序遍历
 * 请构造二叉树并返回其根节点。
 * User: xwl
 * Date: 2023-05-22
 * Time: 13:06
 */

class TreeNode3 {
    int val;
    TreeNode3 left;
    TreeNode3 right;
    TreeNode3() {}
    TreeNode3(int val) { this.val = val; }
    TreeNode3(int val, TreeNode3 left, TreeNode3 right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Test3 {

    /**
     * 根据树的先序遍历和中序遍历构造二叉树
     * @param preorder:二叉树的先序遍历
     * @param inorder:树的中序遍历
     * @return null:树为空
     */
    public TreeNode3 buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,preorder.length - 1);
    }

    // 用来遍历书的前序遍历数组
    private int i = 0;

    /**
     *
     * @param preorder:树的前序遍历
     * @param inorder:树的中序遍历
     * @param inbegin:查找根节点的始位置
     * @param inend:查找根节点的末位置
     * @return
     */
    public TreeNode3 buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend) {
        if (inbegin > inend) {
            return null;
        }
        //
        TreeNode3 root = new TreeNode3(preorder[i]);
        //
        int rootIndex = findIndex(inorder, inbegin, inend, preorder[i]);
        i++;
        root.left = buildTreeChild(preorder, inorder, inbegin, rootIndex - 1);
        root.right = buildTreeChild(preorder, inorder, rootIndex + 1, inend);
        return root;
    }

    /**
     * 查找根节点在中序遍历中的位置
     * @param inorder:中序遍历数组
     * @param inbegin:查找根节点的起始位置
     * @param inend:查找根节点的末位置
     * @param key:待查找的根的值
     * @return
     */
    public int findIndex(int[] inorder,int inbegin, int inend, int key) {
        for (int i = inbegin; i <= inend; i++) {
            if (inorder[i] == key) {
                return i;
            }
        }
        return 0;
    }
}
